# Python 2.6.4
# Project Euler, Problem 123
# Copyright 2010 Talha Zaman

from mine import sieveprimes
primes = sieveprimes(300000)
for n in xrange(1, len(primes)):
    p = primes[n-1]
    psq = p**2
    rem = (pow(p-1, n, psq) + pow(p+1, n, psq)) % psq
    if rem>10000000000: break
print n, primes[n-1]
